Minkowski Addition
   HOME

TheInfoList



OR:

In
geometry Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is c ...
, the Minkowski sum (also known as
dilation Dilation (or dilatation) may refer to: Physiology or medicine * Cervical dilation, the widening of the cervix in childbirth, miscarriage etc. * Coronary dilation, or coronary reflex * Dilation and curettage, the opening of the cervix and surgic ...
) of two sets of position vectors ''A'' and ''B'' in
Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...
is formed by adding each vector in ''A'' to each vector in ''B'', i.e., the set : A + B = \. Analogously, the Minkowski difference (or geometric difference) is defined using the complement operation as : A - B = \left(A^c + (-B)\right)^c In general A - B \ne A + (-B). For instance, in a one-dimensional case A = 2, 2/math> and B = 1, 1/math> the Minkowski difference A - B = 1, 1/math>, whereas A + (-B) = A + B = 3, 3 In a two-dimensional case, Minkowski difference is closely related to
erosion (morphology) Erosion (usually represented by ⊖) is one of two fundamental operations (the other being dilation) in morphological image processing from which all other morphological operations are based. It was originally defined for binary images, later bei ...
in
image processing An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
. The concept is named for
Hermann Minkowski Hermann Minkowski (; ; 22 June 1864 – 12 January 1909) was a German mathematician and professor at Königsberg, Zürich and Göttingen. He created and developed the geometry of numbers and used geometrical methods to solve problems in number t ...
.


Example

For example, if we have two sets ''A'' and ''B'', each consisting of three position vectors (informally, three points), representing the vertices of two
triangle A triangle is a polygon with three Edge (geometry), edges and three Vertex (geometry), vertices. It is one of the basic shapes in geometry. A triangle with vertices ''A'', ''B'', and ''C'' is denoted \triangle ABC. In Euclidean geometry, an ...
s in \mathbb^2, with coordinates :A = \ and :B = \ then their Minkowski sum is :A + B = \ which comprises the vertices of a hexagon. For Minkowski addition, the , \, containing only the
zero vector In mathematics, a zero element is one of several generalizations of 0, the number zero to other algebraic structures. These alternate meanings may or may not reduce to the same thing, depending on the context. Additive identities An additive iden ...
, 0, is an
identity element In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
: for every subset ''S'' of a vector space, :S + \ = S. The
empty set In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other ...
is important in Minkowski addition, because the empty set annihilates every other subset: for every subset ''S'' of a vector space, its sum with the empty set is empty: :S + \emptyset = \emptyset. For another example, consider the Minkowski sums of open or closed balls in the field \mathbb, which is either the
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s \R or
complex number In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form ...
s \C. If B_r := \ is the closed ball of radius r \in , \infty/math> centered at 0 in \mathbb then for any r, s \in , \infty B_r + B_s = B_ and also c B_r = B_ will hold for any scalar c \in \mathbb such that the product , c, r is defined (which happens when c \neq 0 or r \neq \infty). If r, s, and c are all non-zero then the same equalities would still hold had B_r been defined to be the open ball, rather than the closed ball, centered at 0 (the non-zero assumption is needed because the open ball of radius 0 is the empty set). The Minkowski sum of a closed ball and an open ball is an open ball. More generally, the Minkowski sum of an open subset with other set will be an open subset. If G = \left\ is the
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...
of f(x) = \frac and if and Y = \ \times \R is the y-axis in X = \R^2 then the Minkowski sum of these two closed subsets of the plane is the
open set In mathematics, open sets are a generalization of open intervals in the real line. In a metric space (a set along with a distance defined between any two points), open sets are the sets that, with every point , contain all points that are suf ...
G + Y = \ = \R^2 \setminus Y consisting of everything other than the y-axis. This shows that the Minkowski sum of two
closed set In geometry, topology, and related branches of mathematics, a closed set is a set whose complement is an open set. In a topological space, a closed set can be defined as a set which contains all its limit points. In a complete metric space, a cl ...
s is not necessarily a closed set. However, the Minkowski sum of two closed subsets will be a closed subset if at least one of these sets is also a
compact subset In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space by making precise the idea of a space having no "punctures" or "missing endpoints", i. ...
.


Convex hulls of Minkowski sums

Minkowski addition behaves well with respect to the operation of taking
convex hull In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
s, as shown by the following proposition: :For all non-empty subsets S_1 and S_2 of a real vector space, the convex hull of their Minkowski sum is the Minkowski sum of their convex hulls: ::\operatorname(S_1 + S_2) = \operatorname(S_1) + \operatorname(S_2). This result holds more generally for any finite collection of non-empty sets: :\operatorname\left(\sum\right) = \sum\operatorname(S_n). In mathematical terminology, the
operation Operation or Operations may refer to: Arts, entertainment and media * ''Operation'' (game), a battery-operated board game that challenges dexterity * Operation (music), a term used in musical set theory * ''Operations'' (magazine), Multi-Ma ...
s of Minkowski summation and of forming
convex hull In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
s are
commuting Commuting is periodically recurring travel between one's place of residence and place of work or study, where the traveler, referred to as a commuter, leaves the boundary of their home community. By extension, it can sometimes be any regul ...
operations. If S is a convex set then \mu S + \lambda S is also a convex set; furthermore :\mu S + \lambda S = (\mu + \lambda)S for every \mu,\lambda \geq 0. Conversely, if this "
distributive property In mathematics, the distributive property of binary operations generalizes the distributive law, which asserts that the equality x \cdot (y + z) = x \cdot y + x \cdot z is always true in elementary algebra. For example, in elementary arithmetic, ...
" holds for all non-negative real numbers, \mu, \lambda, then the set is convex. The figure to the right shows an example of a non-convex set for which A + A \supsetneq 2 A. An example in 1 dimension is: B =
, 2 The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline ...
\cup
, 5 The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline ...
It can be easily calculated that 2 B =
, 4 The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline ...
\cup
, 10 The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline o ...
/math> but B + B =
, 4 The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline ...
\cup , 7\cup
, 10 The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline o ...
hence again B + B \supsetneq 2 B. Minkowski sums act linearly on the perimeter of two-dimensional convex bodies: the perimeter of the sum equals the sum of perimeters. Additionally, if K is (the interior of) a
curve of constant width In geometry, a curve of constant width is a simple closed curve in the plane whose width (the distance between parallel supporting lines) is the same in all directions. The shape bounded by a curve of constant width is a body of constant width or ...
, then the Minkowski sum of K and of its 180^ rotation is a disk. These two facts can be combined to give a short proof of
Barbier's theorem In geometry, Barbier's theorem states that every curve of constant width has perimeter times its width, regardless of its precise shape. This theorem was first published by Joseph-Émile Barbier in 1860. Examples The most familiar examples of ...
on the perimeter of curves of constant width.


Applications

Minkowski addition plays a central role in
mathematical morphology Mathematical morphology (MM) is a theory and technique for the analysis and processing of geometrical structures, based on set theory, lattice theory, topology, and random functions. MM is most commonly applied to digital images, but it can be em ...
. It arises in the brush-and-stroke paradigm of
2D computer graphics 2D computer graphics is the computer-based generation of digital images—mostly from two-dimensional models (such as 2D geometric models, text, and digital images) and by techniques specific to them. It may refer to the branch of computer ...
(with various uses, notably by
Donald E. Knuth Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
in Metafont), and as the
solid sweep The sweep Sw of a solid S is defined as the solid created when a motion M is applied to a given solid. The solid S should be considered to be a set of points in the Euclid Euclid (; grc-gre, Εὐκλείδης; BC) was an ancient Greek ...
operation of
3D computer graphics 3D computer graphics, or “3D graphics,” sometimes called CGI, 3D-CGI or three-dimensional computer graphics are graphics that use a three-dimensional representation of geometric data (often Cartesian) that is stored in the computer for th ...
. It has also been shown to be closely connected to the
Earth mover's distance In statistics, the earth mover's distance (EMD) is a measure of the distance between two probability distributions over a region ''D''. In mathematics, this is known as the Wasserstein metric. Informally, if the distributions are interpreted ...
, and by extension,
optimal transport In mathematics and economics, transportation theory or transport theory is a name given to the study of optimal transportation and allocation of resources. The problem was formalized by the French mathematician Gaspard Monge in 1781.G. Monge. '' ...
.


Motion planning

Minkowski sums are used in
motion planning Motion planning, also path planning (also known as the navigation problem or the piano mover's problem) is a computational problem to find a sequence of valid configurations that moves the object from the source to destination. The term is used ...
of an object among obstacles. They are used for the computation of the configuration space, which is the set of all admissible positions of the object. In the simple model of translational motion of an object in the plane, where the position of an object may be uniquely specified by the position of a fixed point of this object, the configuration space are the Minkowski sum of the set of obstacles and the movable object placed at the origin and rotated 180 degrees.


Numerical control (NC) machining

In
numerical control Numerical control (also computer numerical control, and commonly called CNC) is the automated control of machining tools (such as drills, lathes, mills, grinders, routers and 3D printers) by means of a computer. A CNC machine processes a pi ...
machining, the programming of the NC tool exploits the fact that the Minkowski sum of the cutting piece with its trajectory gives the shape of the cut in the material.


3D solid modeling

In
OpenSCAD OpenSCAD is a free software application for creating solid 3D computer-aided design (CAD) objects. It is a script-only based modeller that uses its own description language; parts can be previewed, but cannot be interactively modified by mouse i ...
Minkowski sums are used to outline a shape with another shape creating a composite of both shapes.


Aggregation theory

Minkowski sums are also frequently used in aggregation theory when individual objects to be aggregated are characterized via sets.


Collision detection

Minkowski sums, specifically Minkowski differences, are often used alongside GJK algorithms to compute
collision detection Collision detection is the computational problem of detecting the intersection (Euclidean geometry), intersection of two or more objects. Collision detection is a classic issue of computational geometry and has applications in various computing ...
for convex hulls in
physics engines A physics engine is computer software that provides an approximate simulation of certain physical systems, such as rigid body dynamics (including collision detection), soft body dynamics, and fluid dynamics, of use in the domains of computer gr ...
.


Algorithms for computing Minkowski sums


Planar case


Two convex polygons in the plane

For two
convex polygon In geometry, a convex polygon is a polygon that is the boundary of a convex set. This means that the line segment between two points of the polygon is contained in the union of the interior and the boundary of the polygon. In particular, it is a ...
s and in the plane with and vertices, their Minkowski sum is a convex polygon with at most + vertices and may be computed in time O( + ) by a very simple procedure, which may be informally described as follows. Assume that the edges of a polygon are given and the direction, say, counterclockwise, along the polygon boundary. Then it is easily seen that these edges of the convex polygon are ordered by polar angle. Let us merge the ordered sequences of the directed edges from and into a single ordered sequence . Imagine that these edges are solid
arrow An arrow is a fin-stabilized projectile launched by a bow. A typical arrow usually consists of a long, stiff, straight shaft with a weighty (and usually sharp and pointed) arrowhead attached to the front end, multiple fin-like stabilizers c ...
s which can be moved freely while keeping them parallel to their original direction. Assemble these arrows in the order of the sequence by attaching the tail of the next arrow to the head of the previous arrow. It turns out that the resulting
polygonal chain In geometry, a polygonal chain is a connected series of line segments. More formally, a polygonal chain is a curve specified by a sequence of points (A_1, A_2, \dots, A_n) called its vertices. The curve itself consists of the line segments co ...
will in fact be a convex polygon which is the Minkowski sum of and .


Other

If one polygon is convex and another one is not, the complexity of their Minkowski sum is O(nm). If both of them are nonconvex, their Minkowski sum complexity is O((mn)2).


Essential Minkowski sum

There is also a notion of the essential Minkowski sum +e of two subsets of Euclidean space. The usual Minkowski sum can be written as :A + B = \left\. Thus, the essential Minkowski sum is defined by :A +_ B = \left\, where ''μ'' denotes the ''n''-dimensional
Lebesgue measure In measure theory, a branch of mathematics, the Lebesgue measure, named after French mathematician Henri Lebesgue, is the standard way of assigning a measure to subsets of ''n''-dimensional Euclidean space. For ''n'' = 1, 2, or 3, it coincides wit ...
. The reason for the term "essential" is the following property of
indicator function In mathematics, an indicator function or a characteristic function of a subset of a set is a function that maps elements of the subset to one, and all other elements to zero. That is, if is a subset of some set , one has \mathbf_(x)=1 if x\i ...
s: while :1_ (z) = \sup_ 1_ (x) 1_ (z - x), it can be seen that :1_ (z) = \mathop_ 1_ (x) 1_ (z - x), where "ess sup" denotes the
essential supremum In mathematics, the concepts of essential infimum and essential supremum are related to the notions of infimum and supremum, but adapted to measure theory and functional analysis, where one often deals with statements that are not valid for ''all' ...
.


''Lp'' Minkowski sum

For ''K'' and ''L'' compact convex subsets in \mathbb^n, the Minkowski sum can be described by the
support function In mathematics, the support function ''h'A'' of a non-empty closed convex set ''A'' in \mathbb^n describes the (signed) distances of supporting hyperplanes of ''A'' from the origin. The support function is a convex function on \mathbb^n. Any n ...
of the convex sets: : h_ = h_K + h_L. For ''p ≥ 1'', Firey defined the Lp Minkowski sum of compact convex sets ''K'' and ''L'' in \mathbb^n containing the origin as : h_^p = h_K^p + h_L^p. By the
Minkowski inequality In mathematical analysis, the Minkowski inequality establishes that the L''p'' spaces are normed vector spaces. Let ''S'' be a measure space, let and let ''f'' and ''g'' be elements of L''p''(''S''). Then is in L''p''(''S''), and we have the tr ...
, the function ''h'' is again positive homogeneous and convex and hence the support function of a compact convex set. This definition is fundamental in the ''L''p Brunn-Minkowski theory.


See also

*
Blaschke sum In convex geometry and the geometry of convex polytopes, the Blaschke sum of two polytopes is a polytope that has a facet parallel to each facet of the two given polytopes, with the same measure. When both polytopes have parallel facets, the meas ...
*
Brunn–Minkowski theorem In mathematics, the Brunn–Minkowski theorem (or Brunn–Minkowski inequality) is an inequality relating the volumes (or more generally Lebesgue measures) of compact subsets of Euclidean space. The original version of the Brunn–Minkowski theor ...
, an inequality on the volumes of Minkowksi sums *
Convolution In mathematics (in particular, functional analysis), convolution is a operation (mathematics), mathematical operation on two function (mathematics), functions ( and ) that produces a third function (f*g) that expresses how the shape of one is ...
*
Dilation Dilation (or dilatation) may refer to: Physiology or medicine * Cervical dilation, the widening of the cervix in childbirth, miscarriage etc. * Coronary dilation, or coronary reflex * Dilation and curettage, the opening of the cervix and surgic ...
*
Erosion Erosion is the action of surface processes (such as water flow or wind) that removes soil, rock, or dissolved material from one location on the Earth's crust, and then transports it to another location where it is deposited. Erosion is distin ...
*
Interval arithmetic Interval arithmetic (also known as interval mathematics, interval analysis, or interval computation) is a mathematical technique used to put bounds on rounding errors and measurement errors in mathematical computation. Numerical methods using ...
*
Mixed volume In mathematics, more specifically, in convex geometry, the mixed volume is a way to associate a non-negative number to an of convex bodies in space. This number depends on the size and shape of the bodies and on their relative orientation to each ...
(a.k.a.
Quermassintegral In mathematics, more specifically, in convex geometry, the mixed volume is a way to associate a non-negative number to an of convex bodies in space. This number depends on the size and shape of the bodies and on their relative orientation to each ...
or intrinsic volume) *
Parallel curve A parallel of a curve is the envelope of a family of congruent circles centered on the curve. It generalises the concept of '' parallel (straight) lines''. It can also be defined as a curve whose points are at a constant '' normal distance'' f ...
*
Shapley–Folkman lemma The Shapley–Folkman  lemma is a result in convex geometry that describes the Minkowski addition of sets in a vector space. It is named after mathematicians Lloyd Shapley and Jon Folkman, but was first published by the economist Ros ...
*
Sumset In additive combinatorics, the sumset (also called the Minkowski sum) of two subsets A and B of an abelian group G (written additively) is defined to be the set of all sums of an element from A with an element from B. That is, :A + B = \. The n-fo ...
* Topological vector space#Properties *
Zonotope In geometry, a zonohedron is a convex polyhedron that is centrally symmetric, every face of which is a polygon that is centrally symmetric (a zonogon). Any zonohedron may equivalently be described as the Minkowski sum of a set of line segments in ...


Notes


References

* * * * * *. *. *. *. * *


External links

* *
Minkowski Sums
in
Computational Geometry Algorithms Library The Computational Geometry Algorithms Library (CGAL) is an open source software library of computational geometry algorithms. While primarily written in C++, Scilab bindings and bindings generated with SWIG (supporting Python and Java for now) ...

The Minkowski Sum of Two Triangles
an
The Minkowski Sum of a Disk and a Polygon
by George Beck,
The Wolfram Demonstrations Project The Wolfram Demonstrations Project is an organized, open-source collection of small (or medium-size) interactive programs called Demonstrations, which are meant to visually and interactively represent ideas from a range of fields. It is hos ...
.
Minkowski's addition of convex shapes
by
Alexander Bogomolny Alexander Bogomolny (January 4, 1948 July 7, 2018) was a Soviet-born Israeli-American mathematician. He was Professor Emeritus of Mathematics at the University of Iowa, and formerly research fellow at the Moscow Institute of Electronics and M ...
: an applet * Wikibooks:OpenSCAD User Manual/Transformations#minkowski by Marius Kintel: Application
Application of Minkowski Addition to robotics
by Joan Gerard {{Topological vector spaces Theorems in convex geometry Convex geometry Binary operations Digital geometry Geometric algorithms Sumsets Variational analysis Abelian group theory Affine geometry Hermann Minkowski